package org.example.test;

/**
 * @author: lynn
 * @Descript: 给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。
 * 沿途经过的数字要累加起来。返回最小的路径和。
 * @date: 2021/3/4 22:57
 * @version: 1.0
 */
public class MinPathSum {
    public static void main(String[] args) {
        int matrix[][] = {
                { 9, 1, 0, 1 },
                { 4, 8, 1, 0 },
                { 1, 4, 2, 3 }
        };
        System.out.println(minPathSum(matrix, 0, 0)); //14
    }

    /**
     * 从矩阵matrix的(i,j)位置走到右下角元素，返回最小沿途元素和。每个位置只能向右或向下
     *
     * @param matrix
     * @param i
     * @param j
     * @return 最小路径和
     */
    public static int minPathSum(int matrix[][], int i, int j) {
        // 如果(i,j)就是右下角的元素
        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            return matrix[i][j];
        }
        // 如果(i,j)在右边界上，只能向下走
        if (j == matrix[0].length - 1) {
            return matrix[i][j] + minPathSum(matrix, i + 1, j);
        }
        // 如果(i,j)在下边界上，只能向右走
        if (i == matrix.length - 1) {
            return matrix[i][j] + minPathSum(matrix, i, j + 1);
        }
        // 不是上述三种情况，那么(i,j)就有向下和向右两种决策，取决策结果最小的那个
        int left = minPathSum(matrix, i, j + 1);
        int down = minPathSum(matrix, i + 1, j);
        return matrix[i][j] + Math.min(left,down );
    }
}
